Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11116 - Babel towers / 11116.by.Jan.cpp
blobddd084b9291a714e9eaaaa9b6290c3f2222e53ca
1 /*
2 Author : Jan
3 Problem Name : Babel Towers
4 Algorithm : Math, Center of Masses
5 Complexity : O(n^2)
6 */
8 #include <vector>
9 #include <list>
10 #include <map>
11 #include <set>
12 #include <queue>
13 #include <stack>
14 #include <algorithm>
15 #include <iostream>
16 #include <cstdio>
17 #include <cmath>
18 #include <cstdlib>
19 #include <cctype>
20 #include <string>
22 using namespace std;
24 #define min(a,b) ((a) < (b) ? (a) : (b))
25 #define max(a,b) ((a) > (b) ? (a) : (b))
27 #define CLR(a) memset(a,0,sizeof(a))
29 #define MAX 1001
30 const double eps = 1e-7;
32 int n;
33 double sumMass[MAX],sumX[MAX],sumY[MAX];
35 struct circle
37 double x,y,r;
38 }C[MAX];
40 bool input()
42 scanf("%d",&n);
43 if(!n) return false;
44 for(int i=1;i<=n;i++)
46 scanf("%lf %lf %lf",&C[i].x,&C[i].y,&C[i].r);
47 sumX[i]=sumX[i-1]+C[i].x*C[i].r*C[i].r;
48 sumY[i]=sumY[i-1]+C[i].y*C[i].r*C[i].r;
49 sumMass[i]=sumMass[i-1]+C[i].r*C[i].r;
51 return true;
54 void process()
56 int i,j;
57 double sX,sY,sM,X,Y;
59 for(i=1;i<=n;i++)
61 for(j=i-1;j>=1;j--)
63 sM=sumMass[i]-sumMass[j];
64 sX=sumX[i]-sumX[j];
65 sY=sumY[i]-sumY[j];
66 X=sX/sM;
67 Y=sY/sM;
68 if((X-C[j].x)*(X-C[j].x)+(Y-C[j].y)*(Y-C[j].y)+eps>C[j].r*C[j].r)
69 break;
71 if(j) break;
73 if(i==n+1) puts("Feasible");
74 else printf("Unfeasible %d\n",i-1);
77 int main()
79 while(input())
81 process();
83 return 0;